#pragma once
class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_set(n, -1)
	{}
	int FindRoot(int x)
	{
		while (_set[x] >= 0)
			x = _set[x];
		return x;
	}
	void Union(int x, int y)
	{
		int root1 = FindRoot(x);
		int root2 = FindRoot(y);

		if (abs(_set[root1]) < abs(_set[root2]))
			swap(root1, root2);

		if (root1 != root2)
		{
			_set[root1] += _set[root2];
			_set[root2] = root1;
		}
	}
	int SetCount()
	{
		int size = 0;
		for (auto e : _set)
		{
			if (e < 0)
				size++;
		}
		return size;
	}
	bool InSet(int x, int y)
	{
		int root1 = FindRoot(x);
		int root2 = FindRoot(y);

		return root1 == root2;
	}
private:
	vector<int> _set;
};